public class Leetcode746 {
    public static void main(String[] args) {
        System.out.println(minCostClimbingStairs(new int[]{10, 15, 20}));
        System.out.println(minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
    }

    public static int minCostClimbingStairs(int[] cost) {
        Integer[] dp = new Integer[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = Math.min(cost[0], cost[1]);

        return dp(cost, dp, cost.length);
    }

    private static int dp(int[] money, Integer[] dp, int n) {
        if (dp[n] != null) {
            return dp[n];
        }

        dp[n] = Math.min(dp(money, dp, n - 1) + money[n - 1], dp(money, dp, n - 2) + money[n - 2]);

        return dp[n];
    }

    public int minCostClimbingStairs1(int[] cost) {
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}
